package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-05-06 9:14
 */
public class LongestCommonSubsequence {
    /**
     * 相对于此前的数组下标的含义为以i-1 和 j-1结尾的元素所对应符合要求的元素数量，两个子序列的公共子串存在的问题是如果按照这种定义dp的方式，我们需要
     * 从前往后重新进行遍历寻找最大值，所以我们采用另一种定义方式：dp[i][j]代表以i-1和j-1范围内的元素对应的最大值
     * 五部曲：1.dp[i][j] 以0- i-1 和0- j-1范围内的元素寻找其最长公共子串 2.递推公式：i-1== j- 1 dp[i][j]=dp[i-1][j-1]+1
     * 如果不等,延续最大的状态即可:dp[i][j]=max(dp[i][j-1],dp[i-1][j]) 遍历顺序：从前往后遍历 初始化：第一行和第一列都是无效位置，都初始化为0即可
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        //创建dp数组
        int n1=text1.length()+1;
        int n2=text2.length()+1;
        int[][]dp=new int[n1][n2];
        //循环创建
        for(int i=1;i<n1;++i){
            for(int j=1;j<n2;++j){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[n1-1][n2-1];
    }
}

